1. Field of the Invention
The present invention relates to a truncated maximum likelihood sequence estimator. In particular, the present invention relates to an apparatus for providing a best estimate of signals transmitted over a Wireless Local Area Network (WLAN).
2. Discussion of the Related Art
Digital wireless communication systems are used to convey a variety of information between multiple locations. With digital communications, information is translated into a digital or binary form, referred to as bits, for communication purposes. A transmitter maps this bit stream into a modulated symbol stream, converts the modulated symbol stream to a high frequency radio signal and transmits the high frequency radio signal. A digital receiver receives the high frequency radio signal, down converts the radio signal to a low frequency signal, samples the low frequency signal and maps the sampled signal back into an estimate of the information. In digital wireless communications, the wireless radio environment presents many difficulties that impede successful communications. For example, one difficulty is that the signal level can fade; one of the reasons for fading is that the signal may travel multiple paths due to reflections, causing multiple signal images to arrive at the receiver antenna out of phase and in time-varying relationships. This type of fading is commonly referred to as Rayleigh fading. When the signal fades, a signal-to-noise ratio of the signal becomes lower, causing degradation in the quality of the communication link.
A second problem occurs when the multiple signal paths are much different in length. In this case, time dispersion occurs, wherein multiple fading (i.e. of time-varying magnitude) signal images arrive at the receive antenna at different times, thus giving rise to signal echoes. This causes intersymbol interferences (ISI), where the echoes of one symbol interfere with reception of subsequent symbols transmitted.
A third problem occurs when the signal is passed through a narrow band-pass filter at the transmitter, at the receiver, or at both the transmitter and receiver. The narrow band-pass filter is typically used at the transmitter to reduce signal emissions outside of the frequency band allocated to the signal. A narrow band-pass filter is also typically used at the receiver to mitigate the effect of other signals and noise occupying adjacent frequency channels. However, the long response time of typical narrow band-pass filters also introduces ISI into the signal. In addition, finite bandwidth devices such as, for example, a frequency discriminator commonly used in the digital receiver to demodulate Frequency Shift Keyed (FSK) signals, also introduce ISI.
At the receiver, coherent demodulation is desirable because it provides the best performance. However, this requires knowledge of the multi-path channel. In addition, in many wireless applications, this channel may be time varying due to, for example, transmitter motion, receiver motion, and/or atmosphere effects such as scatterer motion. Thus, there may be a need to track properties of a time varying multi-path channel.
To reduce the ISI resulting from any of the above-described mechanisms, it is known that a Maximum-Likelihood-Sequence-Estimation (MLSE) equalizer may be employed. Such an equalizer considers various hypotheses for the transmitted symbol sequence, and, with a model of the dispersive channel, determines which hypothesis best fits the received data. This can be efficiently realized using the Viterbi Algorithm. This equalization technique is well-known to those skilled in the art, and can be found in standard text books such as J. G. Proakis, Digital Communications, 2d ed., NY: McGraw-Hill, chapter 6, 1989.
However, a problem with the MLSE equalizer is that it is highly complex because, for example, the MLSE equalizer is based upon the assumption that ISI extends over the entire transmitted message and that the communication channel varies with time. Thus, implementation of the MLSE is expensive, requires a lot of hardware and/or software resources, and is power-consuming. Accordingly, a decision feedback equalizer (DFE) has been suggested as an alternative to the MLSE.
Referring to FIG. 1, there is illustrated a linear DFE as known to those of skill in the art and as described, for example, in an article titled "An Adaptive RAM-DFE for Storage Channels", IEEE Transactions on Communications, Vol. 39, No. 11, November 1991. At the receiver, a received signal is typically filtered, amplified, mixed down to a baseband signal and sampled at least once every symbol period of the transmitted signal to yield a stream of samples y.sub.k. The samples y.sub.k on line 140 are provided to a feed forward filter 142 having L corresponding feed forward coefficients or weights represented by vector w=w.sub.0 . . . w.sub.L-1 !'. An output of the feed forward filter on line 144 is a product of the feed forward coefficients and the sampled output w'y.sub.k where y.sub.k is a vector of sampled outputs. A sequence of past decisions a.sub.k output by a decision block 146 is also provided on line 148 to a Finite Impulse Response (FIR) filter 150 in a decision feedback section of the DFE. The FIR filter has M corresponding coefficients represented by vector b=b.sub.1 . . . b.sub.M !'and an output of the FIR filter is b'a.sub.k which is provided on line 152 to a summing block 154. In an optimal case, the FIR filter is a model of the ISI of the channel or a causal spectral factor of the channel autocorrelation. The output from the FIR filter b'a.sub.k is subtracted from the feed forward filter output w'y.sub.k to cancel the ISI in a least-square manner. The output z.sub.k of the summing block on line 155 is: EQU z.sub.k =w'y.sub.k +b'a.sub.k ( 1)
Accordingly, an appropriate setting for the coefficient vectors in the DFE minimizes the mean-square error Ee.sub.k.sup.2 !, where: EQU e.sub.k =a.sub.k -z.sub.k ( 2)
However, one problem with the DFE of FIG. 1 as known to those of skill in the art is that it is only capable of eliminating linear ISI. Accordingly, there is a need for a DFE that is capable of canceling non-linear ISI.
FIG. 2 illustrates a RAM-DFE that has been proposed as a solution to this problem. FIG. 2 illustrates the DFE of FIG. 1, wherein the FIR filter 150 has been replaced by a lookup table 102 to comprise the RAM-DFE as illustrated in FIG. 2. The RAM-DFE is described, for example, in the previously cited article entitled "An Adaptive RAM-DFE for Storage Channels", IEEE Transactions on Communications Vol. 39, No. 11, November 1991; as well as an article entitled "A Comparison of Maximum Likelihood Sequence Detection and Non-linear Decision Feedback Equalization on the Digital Magnetic Recording Channel", published in the record of the conference GLOBECOM '91 in 1991. For the RAM DFE of FIG. 2, M past decisions of a.sub.k are arranged in a vector and used as a lookup table address, and the contents of the address location are interpreted as the corresponding lookup table output. An analysis of the RAM-DFE of FIG. 2 is then the same as that of the DFE of FIG. 1.
The effects of time varying channels can be accounted for in the DFE of FIG. 1 by updating the coefficients or "weights" on the taps of the FIR filter 150. This is done by well known techniques such as Least Means Square (LMS) filtering, described in an article entitled "Stationary and Non-Stationary Learning Characteristics of the LMS Adaptive Filter", Proceedings of the IEEE, Vol. 64, No. 8, August 1976. Similarly, the effects of time varying channels can be accounted for in the RAM-DFE of FIG. 2 by updating the contents of the look-up table 102 by, for example, methods described in the previously cited article titled "An Adaptive RAM-DFE for Storage Channels", IEEE Transactions of Communications, Vol. 39, No. 11, November 1991. However, updating the coefficients for either of the DFE of FIG. 1 or the RAM-DFE of FIG. 2 adds further complexity to the equalizer, thus requiring further hardware or software resources, power and expense.
In FIGS. 1 and 2, it can be seen that a decision a.sub.k on a current sample, on line 149, is a function of several future samples to be processed on line 140 and several decisions already made on past samples on line 148.
In addition, the DFE of FIG. 1 requires several coefficients in both filter 142 and filter 150 and the RAM-DFE of FIG. 2 also requires several coefficients in filter 142. Further, decision thresholds which are used by the DFE to make a best estimate of the sequence of the transmitted signal, are fixed for both the DFE of FIG. 1 and the RAM-DFE of FIG. 2. Thus, where there is a need for several decision thresholds such as, for example, where the DFE is to make a best estimate of a received symbol of a 4-ary FSK signal, the difference between the thresholds is fixed and cannot be varied as a function of the received sequence of data samples. Accordingly, there is a need for a DFE that allows for variation of the decision thresholds.
Another alternative that has been used by those of skill in the art to reduce the ISI is a conventional lookup table processor such as is illustrated in FIGS. 3-4. FIG. 3 illustrates a functional block diagram of a DFE for a 4-ary Frequency Shift Keyed (FSK) transmitted signal. A 4-ary FSK transmitted signal is modulated with any of four different frequencies to encode the symbol information transmitted as the FSK signal. In particular, for a 4-ary FSK transmitted signal, the transmitted signal can take on any one of four states: a first state corresponding to a digital sequence "00"; a second state corresponding to a digital sequence "01"; a third state corresponding to a digital sequence "11"; and a fourth state corresponding to a digital sequence "10". The DFE of FIG. 3 determines a most likely sequence oftransmitted bits, one bit of the sequence at a time, using a current sample a.sub.0 of the 4-ary received FSK signal, a next sample a.sub.1 of the received signal, a decision d.sub.-1 made on a previous sample of the received signal, and a decision d.sub.-2 made on a previous to the previous sample of the received signal.
For example, an 8-bit next sample a.sub.1 of the received signal may be provided on line 100 to the lookup table 102. In addition, the next sample is delayed by one clock cycle with delay element 104 to provide to the lookup table on line 106 a current 8-bit sample a.sub.0 of the received signal. The lookup table contains a plurality of weights w.sub.i used to compute a value of the input signal y.sub.0 with reduced ISI according to equation (3): EQU y.sub.0 =a.sub.1 w.sub.1 +a.sub.0 w.sub.0 +d.sub.-1 w.sub.-1 +d.sub.-2 w.sub.-2 ( 3)
A reduced ISI input signal y.sub.0 is then compared with three fixed threshold values tf.sub.i, where i=1,2,3, to provide at an output on line 108 a 2-bit decision d.sub.0. In particular, the reduced ISI signal y.sub.0 is compared against the three fixed threshold values tf.sub.1, tf.sub.2 and tf.sub.3 to make the 2-bit decision d.sub.0 on the current sample. Thus, the conventional lookup table processor provides at the output on line 108 the 2-bit decision d.sub.0 on the current sample. In addition, the decision on the current sample is delayed by delay element 110 to provide on line 112 to the lookup table the 2-bit decision d.sub.-1 on the previous sample. Further the decision d.sub.-1 is delayed by delay element 114 to provide on line 116 to the lookup table, the 2-bit decision d.sub.-2 on the previous to the previous sample.
However, the lookup table 102A of the conventional lookup table processor of FIG. 3 requires a minimum of twenty bits of input capacity: eight bits for the next sample a.sub.-1, eight bits for the current sample a.sub.0, two bits for the decision d.sub.-1 made on the previous sample and two bits for the decision d.sub.-2 made on the previous to the previous sample. In particular, the lookup table requires a minimum of 2.sup.20 or 1,048,576 memory locations wherein each memory location has at least two bits of capacity to store the decision d.sub.0 from the current sample. Thus, the lookup table requires a minimum of 2,097,152 bits of total capacity.
FIG. 4 illustrates a functional block diagram implementing a conventional lookup table processor for a 2-ary FSK transmitted signal. A 2-ary FSK transmitting signal can be modulated with one of two frequencies to encode digital information which can take on one of two states; a digital "0" or a digital "1". The DFE of FIG. 4 determines a most likely sequence of transmitted bits, one bit of the sequence at a time, using a current sample a.sub.0 of the received 2-ary FSK transmitted signal, a next sample a.sub.1 of the received signal, a sample after the next sample a.sub.2 of the received signal, a decision d.sub.-1 made on a previous sample of the received signal, and a decision made on a previous to the previous sample of the received signal.
For example, a 6-bit sample after the next sample a.sub.2 of the received signal is provided to a lookup table 102B on line 118. In addition, the 6-bit sample is delayed by one clock cycle with delay element 120 to provide a 6-bit next sample a.sub.1 on line 122 to the lookup table. The 6-bit next sample is also delayed by one clock cycle with delay element 124 to provide on line 126 a current 6-bit sample a.sub.0 to the lookup table. The lookup table operates in a manner as similar to that described above with respect to FIG. 2. In particular, the lookup table determine a value of the input signal with reduced ISI y.sub.0 according to Equation (4): EQU y.sub.0 =a.sub.2 w.sub.2 +a.sub.1 w.sub.1 +a.sub.0 w.sub.0 +d.sub.-1 w.sub.-1 +d.sub.-2 w.sub.-2 ( 4)
A reduced ISI signal y.sub.0 is compared to a fixed threshold value t.sub.v and a 1-bit decision d.sub.0 is output on line 128. Thus, the lookup table 102B provides at the output on line 128 a 1-bit decision d.sub.0 on the current sample. In addition, the decision on the current sample is delayed by delay element 130 to provide on line 132 to the lookup table a 1-bit decision d.sub.-1 on the previous sample. Further, the decision d.sub.-1 is delayed by delay element 134 to provide on line 136 to the lookup table a 1-bit decision d.sub.-2 on the previous to the previous sample.
However, the lookup table of the DFE of FIG. 4 requires at a minimum twenty bits of address for an input: six bits for a sample after the next sample a.sub.2 ; six bits for the next sample a.sub.1 ; six bits for the current sample a.sub.0 ; one bit for the decision made on the previous sample d.sub.-1 ; and one bit for the decision made on the previous to the previous sample d.sub.-2. In other words, the lookup table requires 2.sup.20 or 1,048,576 memory locations each having at least one bit of capacity to store the decision d.sub.0 on the current sample or in other words 1,048,576 bits of total capacity.
It is accordingly an object of the present invention to improve upon the conventional lookup table processor, the DFE and the MLSE of the related art.